#include<iostream> 
#include<vector>
using namespace std;

class Solution1 {
public:
    int strStr(string haystack, string needle) {
        if(needle == "")return 0;
        for(int i = 0; i < haystack.length(); i++){
            if(haystack.substr(i, needle.length()) == needle)return i;
        }
        return -1;
    }
};

// 2020.10.16
// 懒得写 kmp 了后面再写，反正是简单题 (

class Solution {
public:
    vector<int> *getNext(string &pattern)
    {
        int j = 0, k = -1;
        vector<int> *next = new vector<int>(pattern.length());
        (*next)[0] = -1;
        while (j + 1 < pattern.length()) {
            if (k == -1 || pattern[j] == pattern[k]) {
                (*next)[++j] = ++k;
            } else {
                k = (*next)[k];
            }
        }
        return next;
    }

    int kmp(string &primary, string &pattern)
    {
        int i = 0, j = 0;
        vector<int> &next = *getNext(pattern);
        while (j < (int)pattern.length() && i < (int)primary.length()) {
            if (j == -1 || primary[i] == pattern[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        delete &next;
        if (j == pattern.length()) {
            return i - j;
        } else {
            return -1;
        }
    }

    int strStr(string haystack, string needle)
    {
        return kmp(haystack, needle);
    }
};

int main(){
    string pattern = "ll", primary = "hello";
    Solution a;
    cout << a.strStr(primary, pattern);
    return 0;
}

// 2022.8.30
// kmp 写法